/**
 * 给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的key对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
 *
 * 一般来说，删除节点可分为两个步骤：
 *
 * 首先找到需要删除的节点；
 * 如果找到了，删除它。
 *
*思路：迭代
 * https://leetcode.cn/problems/delete-node-in-a-bst/
 */
class DeleteNodeDieDai {
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root==null){
            return null;
        }
       TreeNode cur=root;
       TreeNode pre=null;
       while(cur!=null){
           if(cur.val<key){
               pre=cur;
               cur=cur.right;
           }else if(cur.val>key){
               pre=cur;
               cur=cur.left;
           }else{
               if(cur.right==null){
                   if(cur==root){
                       root=root.left;
                   }else if(pre.left==cur){
                       pre.left=cur.left;
                   }else{
                       pre.right=cur.left;
                   }
                   break;
               }else if(cur.left==null){
                   if(cur==root){
                       root=root.right;
                   }else if(pre.left==cur){
                       pre.left=cur.right;
                   }else{
                       pre.right=cur.right;
                   }
                   break;
               }else{
                   TreeNode preParent=cur;
                   TreeNode node=cur.right;
                   while(node.left!=null){
                       preParent=node;
                       node=node.left;
                   }
                   int tmp=node.val;
                   node.val=cur.val;
                   cur.val=tmp;
                   if(preParent.left==node){
                       preParent.left=node.right;
                   }else{
                       preParent.right=node.right;
                   }
                   break;
               }
           }
       }
       return root;
    }
}